#pragma once

#include <utility>
#include <vector>
#include <stack>
#include <queue>

template<class T>
struct binary_node
{
private:
	typedef T data_type;
	
	typedef binary_node<data_type> self;
	typedef self* self_pointer;
public:
	explicit binary_node(const data_type& data)
		: _data(data)
	{}
	explicit binary_node(data_type&& data = data_type())
		: _data(std::forward<data_type>(data))
	{}
	template<class... Args>
	explicit binary_node(Args&&... args)
		: _data(args...)
	{}

	virtual void swap(self& right)
	{
		std::swap(_data, right._data);
		std::swap(_pLeft, right._pLeft);
		std::swap(_pRight, right._pRight);
	}

	data_type _data = data_type();
	self_pointer _pLeft = nullptr;
	self_pointer _pRight = nullptr;
};

template<class T>
class binary_tree
{
	typedef T data_type;

	typedef struct binary_node<data_type> binary_node;
	typedef binary_node* node_pointer;

	typedef binary_tree<data_type> self;
public:
	node_pointer& get_root()
	{
		return _root;
	}

	std::vector<data_type> pre_order() const
	{
		std::vector<data_type> ret;
		std::stack<node_pointer> st;
		st.push(_root);
		while (!st.empty())
		{
			node_pointer node = st.top();
			st.pop();
			ret.push_back(node->_data);
			if (node->_pRight != nullptr)
				st.push(node->_pRight);
			if (node->_pLeft != nullptr)
				st.push(node->_pLeft);
		}
		return ret;
	}
	std::vector<data_type> in_order() const
	{
		std::vector<data_type> ret;
		std::stack<node_pointer> st;
		node_pointer node = _root;
		while (node || !st.empty())
		{
			while (node)
			{
				st.push(node);
				node = node->_pLeft;
			}
			node_pointer top = st.top();
			st.pop();
			ret.push_back(top->_data);
			if (top->_pRight)
				node = top->_pRight;
		}
		return ret;
	}
	std::vector<data_type> post_order() const
	{
		std::vector<data_type> ret;
		std::stack<node_pointer> st;
		node_pointer node = _root;
		node_pointer prev = nullptr;
		while (node || !st.empty())
		{
			while (node)
			{
				st.push(node);
				node = node->_pLeft;
			}
			node_pointer top = st.top();
			if (top->_pRight == nullptr || top->_pRight == prev)
			{
				st.pop();
				ret.push_back(top->_data);
				prev = top;
			}
			else
				node = top->_pRight;
		}
		return ret;
	}
	std::vector<data_type> level_order() const
	{
		std::vector<data_type> ret;
		std::queue<node_pointer> q;
		q.push(_root);
		while (!q.empty())
		{
			size_t size = q.size();
			for (size_t i = 0; i < size; ++i)
			{
				node_pointer node = q.front();
				q.pop();
				ret.push_back(node->_data);
				if (node->_pLeft != nullptr)
					q.push(node->_pLeft);
				if (node->_pRight != nullptr)
					q.push(node->_pRight);
			}
		}
		return ret;
	}

	size_t leaf_count() const
	{
		size_t ret = 0;
		std::queue<node_pointer> q;
		q.push(_root);
		while (!q.empty())
		{
			size_t size = q.size();
			for (size_t i = 0; i < size; ++i)
			{
				node_pointer node = q.front();
				q.pop();
				if (node->_pLeft != nullptr)
					q.push(node->_pLeft);
				if (node->_pRight != nullptr)
					q.push(node->_pRight);
				if (node->_pLeft == nullptr && node->_pRight == nullptr)
					++ret;
			}
		}
		return ret;
	}
	size_t height() const
	{
		size_t ret = 0;
		std::queue<node_pointer> q;
		q.push(_root);
		while (!q.empty())
		{
			size_t size = q.size();
			for (size_t i = 0; i < size; ++i)
			{
				node_pointer node = q.front();
				q.pop();
				if (node->_pLeft != nullptr)
					q.push(node->_pLeft);
				if (node->_pRight != nullptr)
					q.push(node->_pRight);
			}
			++ret;
		}
		return ret;
	}

protected:
	node_pointer _root = nullptr;
};

